public class Prog {

}
//删除链表的倒数第n个节点
//import java.util.*;
//
///*
// * public class ListNode {
// *   int val;
// *   ListNode next = null;
// * }
// */
//
//public class Solution {
//    /**
//     *
//     * @param head ListNode类
//     * @param n int整型
//     * @return ListNode类
//     */
//
//    public ListNode removeNthFromEnd (ListNode head, int n) {
//        // write code here
//        ListNode newhead=new ListNode(-1);
//        newhead.next=head;
//        ListNode fast=newhead;
//        ListNode slow=newhead;
//        for(int i=1;i<=n+1;i++){
//            fast=fast.next;
//        }
//        while(fast!=null){
//            slow=slow.next;
//            fast=fast.next;
//        }
//        slow.next=slow.next.next;
//        return newhead.next;
//    }
//}













//删除有序链表中重复的元素-II
//import java.util.*;
//
///*
// * public class ListNode {
// *   int val;
// *   ListNode next = null;
// * }
// */
//
//public class Solution {
//    /**
//     *
//     * @param head ListNode类
//     * @return ListNode类
//     */
//    public ListNode deleteDuplicates (ListNode head) {
//        // write code here
//        ListNode newhead=new ListNode(-1);
//        newhead.next=head;
//        ListNode prev=newhead;
//        ListNode cur=head;
//        while(cur!=null&&cur.next!=null){
//            if(cur.val==cur.next.val){
//                while(cur.next!=null&&cur.val==cur.next.val){
//                    cur=cur.next;
//                }
//                prev.next=cur.next;
//                cur=cur.next;
//            }
//            else{
//                prev=cur;
//                cur=cur.next;
//            }
//        }
//        return newhead.next;
//    }
//}












//单链表的排序
//import java.util.*;
//
///*
// * public class ListNode {
// *   int val;
// *   ListNode next = null;
// * }
// */
//
//public class Solution {
//    /**
//     *
//     * @param head ListNode类 the head node
//     * @return ListNode类
//     */
//    public ListNode sortInList (ListNode head) {
//        // write code here
//        if(head==null||head.next==null)    return head;
//
//        ListNode pre = head;//pre指向已经有序的节点
//        ListNode cur = head.next;//cur指向待排序的节点
//
//        ListNode aux = new ListNode(-1);//辅助节点
//        aux.next = head;
//
//        while(cur!=null){
//            if(cur.val<pre.val){
//                //先把cur节点从当前链表中删除，然后再把cur节点插入到合适位置
//                pre.next = cur.next;
//
//                //从前往后找到l2.val>cur.val,然后把cur节点插入到l1和l2之间
//                ListNode l1 = aux;
//                ListNode l2 = aux.next;
//                while(cur.val>l2.val){
//                    l1 = l2;
//                    l2 = l2.next;
//                }
//                //把cur节点插入到l1和l2之间
//                l1.next = cur;
//                cur.next = l2;//插入合适位置
//
//                cur = pre.next;//指向下一个待处理节点
//
//            }else{
//                pre = cur;
//                cur = cur.next;
//            }
//        }
//        return aux.next;
//    }
//}













/**判断链表中是否有环
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
//public class Solution {
//    public boolean hasCycle(ListNode head) {
//        ListNode fast=head;
//        ListNode slow=head;
//        while(fast!=null&&fast.next!=null){
//            fast=fast.next.next;
//            slow=slow.next;
//            if(fast==slow){
//                return true;
//            }
//        }
//        return false;
//    }
//}











/*两个链表的第一个公共结点
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
//public class Solution {
//    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//        ListNode pl=pHead1;
//        ListNode ps=pHead2;
//        int len1=0;
//        int len2=0;
//        while(pl!=null){
//            len1++;
//            pl=pl.next;
//        }
//        while(ps!=null){
//            len2++;
//            ps=ps.next;
//        }
//        int len=len1-len2;
//        if(len<0){
//            len=len2-len1;
//            pl=pHead2;
//            ps=pHead1;
//        }
//        else{
//            pl=pHead1;
//            ps=pHead2;
//        }
//        while(len>0){
//            len--;
//            pl=pl.next;
//        }
//        while(pl!=ps){
//            pl=pl.next;
//            ps=ps.next;
//        }
//        if(pl==ps){
//            return pl;
//        }
//        return null;
//    }
//}












//划分链表
//import java.util.*;
//
///*
// * public class ListNode {
// *   int val;
// *   ListNode next = null;
// * }
// */
//
//public class Solution {
//    /**
//     *
//     * @param head ListNode类
//     * @param x int整型
//     * @return ListNode类
//     */
//    public ListNode partition (ListNode head, int x) {
//        // write code here
//        if(head==null){
//            return head;
//        }
//        if(head.next==null||head.next.next==null){
//            return head;
//        }
//        ListNode bs=null;
//        ListNode be=null;
//        ListNode as=null;
//        ListNode ae=null;
//        ListNode cur=head;
//        while(cur!=null){
//            if(cur.val<x){
//                if(bs==null){
//                    bs=cur;
//                    be=cur;
//                }
//                else{
//                    be.next=cur;
//                    be=cur;
//                }
//            }
//            else{
//                if(as==null){
//                    as=cur;
//                    ae=cur;
//                }
//                else{
//                    ae.next=cur;
//                    ae=cur;
//                }
//            }
//            cur=cur.next;
//        }
//        if(as==null){
//            be.next=null;
//            return bs;
//        }
//        else{
//            be.next=as;
//            ae.next=null;
//        }
//        if(bs==null){
//            ae.next=null;
//            return as;
//        }
//        return bs;
//    }
//}











//判断一个链表是否为回文结构
//import java.util.*;
//
///*
// * public class ListNode {
// *   int val;
// *   ListNode next = null;
// * }
// */
//
//public class Solution {
//    /**
//     *
//     * @param head ListNode类 the head
//     * @return bool布尔型
//     */
//    public boolean isPail (ListNode head) {
//        // write code here
//        if(head==null){
//            return false;
//        }
//        if(head.next==null){
//            return true;
//        }
//        ListNode fast=head;
//        ListNode slow=head;
//        while(fast!=null&&fast.next!=null){
//            fast=fast.next.next;
//            slow=slow.next;
//        }
//        if(fast!=null){
//            slow=slow.next;
//        }
//        ListNode rl=slow;
//        ListNode prev=null;
//        while(rl!=null){
//            ListNode rlnext=rl.next;
//            rl.next=prev;
//            prev=rl;
//            rl=rlnext;
//        }
//        slow=prev;
//        fast=head;
//        while(slow!=null){
//            if(slow.val!=fast.val){
//                return false;
//            }
//            slow=slow.next;
//            fast=fast.next;
//        }
//        return true;
//    }
//}











//删除有序链表中重复的元素-I
//import java.util.*;
//
///*
// * public class ListNode {
// *   int val;
// *   ListNode next = null;
// * }
// */
//
//public class Solution {
//    /**
//     *
//     * @param head ListNode类
//     * @return ListNode类
//     */
//    public ListNode deleteDuplicates (ListNode head) {
//        // write code here
//        if(head==null){
//            return head;
//        }
//        ListNode cur=head.next;
//        ListNode pre=head;
//        while(cur!=null){
//            if(cur.val==pre.val){
//                pre.next=cur.next;
//                cur=cur.next;
//            }
//            else{
//                pre=cur;
//                cur=cur.next;
//            }
//        }
//        return head;
//    }
//}













/*合并两个排序的链表
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
//public class Solution {
//    public ListNode Merge(ListNode list1,ListNode list2) {
//        ListNode head=new ListNode(-1);
//        ListNode cur=head;
//        while(list1!=null&&list2!=null){
//            if(list1.val<list2.val){
//                cur.next=list1;
//                list1=list1.next;
//            }
//            else{
//                cur.next=list2;
//                list2=list2.next;
//            }
//            cur=cur.next;
//        }
//        if(list1==null){
//            cur.next=list2;
//        }
//        else{
//            cur.next=list1;
//        }
//        return head.next;
//    }
//}















///* 反转链表
//public class ListNode {
//    int val;
//    ListNode next = null;
//
//    ListNode(int val) {
//        this.val = val;
//    }
//}*/
//public class Solution {
//    public ListNode ReverseList(ListNode head) {
//        if(head==null){
//            return head;
//        }
//        if(head.next==null){
//            return head;
//        }
//        ListNode cur=head;
//        ListNode pre=null;
//        while(cur!=null){
//            ListNode curnext=cur.next;
//            cur.next=pre;
//            pre=cur;
//            cur=curnext;
//        }
//        return pre;
//    }
//}